package com.ddl.eurekaclient.algorithm;

public class QuickSort {

	/**
	 * 快速排序实际是基于“二分法”的思想，指定数组中的某一个数为基数，
	 * 两个指针分别从左右两端向对端移动，每移动一个下标则获取这个下标对应的值，
	 * 从左向右移动的会与基数相比 如果大于则停下；小于则继续移动
	 * 从右向左移动的回与基数相比 如果小于则停下；大于则继续移动
	 * 然后交换左右分别大于或者小于的值；
	 * 每一次循环的最终结果是这个基数的左边永远是小于基数的，基数的右边是永远大于基数的
	 * @param arr	要排序的数组
	 * @param low	数组下标
	 * @param high	数组长度
	 */
	public static void quickSort(int[] arr, int low, int high) {
		int i, j, tmp, t;
		if(low > high) {
			return;
		}

		i = low;
		j = high;

		//tmp为基数
		tmp = arr[low];

		while (i<j) {
			//先看右边，依次往左递减
			while(tmp <= arr[j] && i < j) {
				j--;
			}
			//再看左边，依次往右递增
			while (tmp>=arr[i]&&i<j) {
				i++;
			}
			//如果满足条件则交换
			if (i<j) {
				t = arr[j];
				arr[j] = arr[i];
				arr[i] = t;
			}
		}
		//最后将基准为与i和j相等位置的数字交换
		arr[low] = arr[i];
		arr[i] = tmp;
		//递归调用左半数组
		quickSort(arr, low, j-1);
		//递归调用右半数组
		quickSort(arr, j+1, high);
	}

	public static void main(String[] args){
		int[] arr = {10,7,2,4,7,62,3,4,2,1,8,9,19};
		quickSort(arr, 0, arr.length-1);
		for (int i = 0; i < arr.length; i++) {
			System.out.println(arr[i]);
		}

	}

}
